public class SingleLinkedList {
     static class Node{
          public int val;
          public Node next;

          public Node(int val) {
               this.val = val;
          }
     }
     public Node head;
     //头插法
     public void addFirst(int data){
          if(head == null){
               head = new Node(data);
          }else{
               Node cur = new Node(data);
               cur.next = head;
               head = cur;
          }
     }
     //尾插法
     public void addLast(int data){
          if(head == null){
               head = new Node(data);
          }else{
               Node cur = head;
               while(cur.next != null){
                    cur =cur.next;
               }
               Node flagNode = new Node(data);
               cur.next = flagNode;
          }
     }
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data){
          Node cur = head;
          if(index < 0 || index > size()){
               return false;
          }else if (index == 0) {
               addFirst(data);
               return true;
          } else {
               for (int i = 0; i < index - 1; i++) {
                    cur = cur.next;
               }
               Node pre =cur;
               Node flag = new Node(data);
               flag.next = pre.next;
               pre.next = flag;
          }
          return true;

     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
          Node cur = head;
          while(cur != null){
               if(cur.val == key){
                    return true;
               }else {
                    cur = cur.next;
               }
          }
          return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key) {
          if (contains(key)) {
               Node cur = head;
               if (head.val == key) {
                    head = head.next;
                    cur = null;
               }
               while (cur != null) {
                    if (cur.next.val == key) {
                         break;
                    } else {
                         cur = cur.next;
                    }
               }
               cur.next = cur.next.next;
          } else {
               System.out.println("不包含该关键字！");
               return;
          }
     }

     //删除所有值为key的节点
     public void removeAllKey(int key){
          Node cur = head;
          while(cur.next != null){
               if (contains(key)) {

                    if (head.val == key) {
                         head = head.next;
                         cur = null;
                    }
                    while (cur.next != null) {
                         if (cur.next.val == key) {
                              break;
                         } else {
                              cur = cur.next;
                         }
                    }
                    cur.next = cur.next.next;
               }
          }
     }
     //得到单链表的长度
     public int size(){
          Node cur = head;
          int count = 0;
          while(cur != null){
               cur = cur.next;
               count++;
          }
          return count;
     }
     public void display(){
          Node cur = head;
          while(cur != null){
               System.out.print(cur.val+" ");
               cur = cur.next;
          }
          System.out.println();
     }
     public void clear(){
          head = null;
     }
 }